package com.chaos.eurekaproducer.leetCode.sort;

import com.chaos.eurekaproducer.domain.User;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author liaopeng
 * @title: MergeSort
 * @projectName eureka-producer
 * @description: 归并排序
 * @date 2021/7/5下午9:48
 */
public class MergeSort {

    public static void mergeSortA(int[] a){
        mergeSortC(a,0,a.length-1);
    }

    private static void mergeSortC(int[] a, int p, int q) {
        if (p>=q){
            return;
        }
        int r = p+(q-p)/2;
        mergeSortC(a,p,r);
        mergeSortC(a,r+1,q);
        merge(a,p,r,q);
    }

    private static void merge(int[] a, int p, int r, int q) {
        int i=p;
        int j=r+1;
        /**
         * 此处需要额外定义一个存储空间，所以归并排序不是原地排序算法
         */
        int[] temp = new int[q-p+1];
        int m=0;
        while(i<=r && j<=q){
            if (a[i]<=a[j]){
                /**
                 * 当有两个相同元素的时候，我们可以再这里将p-r中的元素先放入temp数组，
                 * 保证了合并前后顺序不变，所以归并排序是稳定的排序算法
                 */
                temp[m++]=a[i++];
            }else{
                temp[m++]=a[j++];
            }
        }
        while (i<=r){
            temp[m++]=a[i++];
        }
        while ((j<=q)){
            temp[m++]=a[j++];
        }
        //再把临时数组复制到a数组
        for (int k =0; k <=q-p; k++) {
            a[p+k]=temp[k];
        }
    }

    public static void main(String[] args) {
        int[] a = {10,2,4,1,12,5,8,3,9,20,24,18,15};
        mergeSortA(a);
        for (int i : a) {
            System.out.println(i);
        }
    }
}
